package LeetCode;

import java.util.PriorityQueue;

public class Code215_findKthLargest {
    // 1.小顶堆，倒数第k个出堆的就是第k大数
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((n1, n2)-> n1 - n2);
        for (int num : nums) {
            heap.add(num);
            if (heap.size() > k){
                heap.poll();
            }
        }
        return heap.poll();
    }

    // 2.大顶堆，第k个出堆的就是第k大数
    public int findKthLargest2(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((n1, n2)-> n2 - n1);
        for (int num : nums) {
            heap.add(num);
        }
        int res = 0;
        for (int i = 0; i < k; i++) {
            res = heap.poll();
        }
        return res;
    }

    // 3.类快排算法
    int index;
    int[] nums;
    public int findKthLargest3(int[] nums, int k) {
        this.index = nums.length - k;
        this.nums = nums;
        recursion(0, nums.length - 1);
        return this.nums[nums.length - k];
    }

    public void recursion(int left, int right){
        int pivot = right;
        while (left < right){
            while (nums[left] <= nums[pivot] && left < right){
                left++;
            }
            while (nums[right] >= nums[pivot] && left < right){
                right--;
            }
            if (left < right){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        // left == right
        int temp = nums[left];
        nums[left] = nums[pivot];
        nums[pivot] = temp;
        if (left < index){
            recursion(left + 1, nums.length - 1);
        } else if (left > index){
            recursion(0, left - 1);
        } else { // 存放位置正确
            return;
        }
    }
}
